using System;
using System.Collections.Generic;
using UnityEngine;
namespace Super
{
	public class MultiTree<T> where T : IMultiTreeNode<T>
	{
		public MultiTreeNode<T> root;
		public MultiTree() { }
		public MultiTree(T value)
		{
			Insert(value);
		}
		public MultiTree(List<T> values)
		{
			foreach (var item in values)
			{
				Insert(item);
			}
		}

		/// <summary>
		/// ����ڵ�
		/// </summary>
		/// <param name="value"></param>
		public void Insert(T value)
		{
			if (root == null)
				root = new MultiTreeNode<T>();
			root = Insert(root, value);
		}

		private MultiTreeNode<T> Insert(MultiTreeNode<T> root, T value)
		{
			if (!value.CheckIfInsertNode(root, value))	//非插入点，向下找出入点
			{
				object key = value.GetMapKey(root, value);
				if (!root.Map.ContainsKey(key))
				{
					InitChildNode(root, key);
				}

				root.Map[key] = Insert(root.Map[key], value);
			}

			value.UpdateNode(this, root, value);
			UpdateHeight(root);

			return root;
		}


		/// <summary>
		/// ���ݽڵ��key���ҽڵ㣬Ч�ʽϸ�
		/// </summary>
		/// <param name="keys"></param>
		/// <returns></returns>
		public MultiTreeNode<T> Find(List<object> keys)
		{
			return Find(root, keys);
		}

		/// <summary>
		/// ����ֵ���ҽڵ㣬Ч�ʺܵ�
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		public MultiTreeNode<T> Find(T value)
		{
			List<MultiTreeNode<T>> multiTreeNodes = GetAllNode(false);
			foreach (var item in multiTreeNodes)
			{
				if (value.Equals(item.value)) return item;
			}
			return null;
		}

		/// <summary>
		/// ʹ�ù��˺���ɸѡ�����в��ң�Ч��һ��
		/// </summary>
		/// <param name="value"></param>
		/// <param name="func"></param>
		/// <returns></returns>
		public MultiTreeNode<T> Find(T value, Func<MultiTreeNode<T>, T, bool> func)
		{
			return Find(root, value, func);
		}


		/// <summary>
		/// ����ֵɾ�����ݣ�Ч�ʽϵ�
		/// </summary>
		/// <param name="value"></param>
		public void Delete(T value)
		{
			Delete(root, value);
		}

		/// <summary>
		/// ����keyɾ�����ݣ�Ч�ʽϸ�
		/// </summary>
		/// <param name="keys"></param>
		/// <returns></returns>
		public MultiTreeNode<T> Delete(List<object> keys)
		{
			MultiTreeNode<T> node = Find(keys.GetRange(0, keys.Count - 1));
			MultiTreeNode<T> deleteNode = null;
			object key = keys[keys.Count - 1];
			if (node != null)
			{
				if (node.Map.ContainsKey(key))
				{
					deleteNode = node.Map[key];
				}
				node.Map.Remove(key);
			}

			return deleteNode;
		}

		/// <summary>
		/// ʹ�ù��˺�����Ȼ�����ֵɾ�����ݣ�Ч��һ��
		/// </summary>
		/// <param name="value"></param>
		/// <param name="func"></param>
		public void Delete(T value, Func<MultiTreeNode<T>, T, bool> func)
		{
			Delete(root, value, func);
		}


		/// <summary>
		/// �����ӽڵ�߶ȣ����½ڵ�߶�
		/// </summary>
		/// <param name="node"></param>
		public void UpdateHeight(MultiTreeNode<T> node)
		{
			int maxHeight = 0;
			foreach (var item in node.Map)
			{
				maxHeight = Mathf.Max(maxHeight, Height(item.Value));
			}
			node.height = maxHeight + 1;
		}

		/// <summary>
		/// ��ȡ�ڵ�ĸ߶�
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public int Height(MultiTreeNode<T> node)
		{
			if (node == null)
				return 0;
			return node.height;
		}

		/// <summary>
		/// ��ʼ���ڵ㣬�������ӽڵ��keys
		/// </summary>
		/// <param name="root"></param>
		/// <param name="key"></param>
		public void InitChildNode(MultiTreeNode<T> root, object key)
		{
			//root.keys��һ��List<object>���͵ļ��϶��󡣵��㽫����Ϊ�������ݸ�List<T>�Ĺ��캯��ʱ��
			//���캯����ݹ�ش���һ���µ�List<object>����
			//���а�����ԭʼ������ͬ��Ԫ�ء�����ݹ���̻᲻�ϵص��ù��캯����
			//ÿ�δ��ݵĲ������Ǽ��϶��������������޵ݹ�ķ�����
			//List<object> keys = new List<object>(root.keys);

			MultiTreeNode<T> childNode = new MultiTreeNode<T>();
			List<object> keys = new List<object>(root.keys);
			keys.Add(key);
			childNode.keys = keys;
			root.Map[key] = childNode;
		}



		/// <summary>
		/// ��ȡ���еĽڵ�
		/// </summary>
		/// <param name="node"></param>
		/// <param name="onlyLeaf"></param>
		/// <returns></returns>
		public List<MultiTreeNode<T>> GetAllNode(bool onlyLeaf = true)
		{

			List<MultiTreeNode<T>> values = new List<MultiTreeNode<T>>();
			GetAllNode(root, values, onlyLeaf);
			return values;
		}


		/// <summary>
		/// ��ȡ�������������нڵ�
		/// </summary>
		/// <param name="func"></param>
		/// <param name="onlyLeaf"></param>
		/// <returns></returns>
		public List<MultiTreeNode<T>> GetAllNode(Func<MultiTreeNode<T>, bool> func, bool onlyLeaf = true)
		{
			List<MultiTreeNode<T>> values = new List<MultiTreeNode<T>>();
			GetAllNode(root, values, func, onlyLeaf);
			return values;
		}

		/// <summary>
		/// ��ȡ�ڵ��£����еĽڵ�
		/// </summary>
		/// <param name="node"></param>
		/// <param name="onlyLeaf"></param>
		/// <returns></returns>
		public List<MultiTreeNode<T>> GetAllNodeByNode(MultiTreeNode<T> node, bool onlyLeaf = true)
		{
			List<MultiTreeNode<T>> values = new List<MultiTreeNode<T>>();
			GetAllNode(node, values, onlyLeaf);
			return values;
		}

		/// <summary>
		/// ��ȡ�ڵ������е�ֵ
		/// </summary>
		/// <param name="node"></param>
		/// <param name="onlyLeaf"></param>
		/// <returns></returns>
		public List<T> GetAllNodeValue(MultiTreeNode<T> node, bool onlyLeaf = true)
		{
			List<T> values = new List<T>();
			GetAllNodeValue(node, values, onlyLeaf);
			return values;
		}

		/// <summary>
		/// ��ȡ���ڵ�
		/// </summary>
		/// <returns></returns>
		public MultiTreeNode<T> GetRootNode()
		{
			return root;
		}

		/// <summary>
		/// ������ڵ�
		/// </summary>
		public void ClearRoot()
		{
			root = null;
		}

		private MultiTreeNode<T> Find(MultiTreeNode<T> root, List<object> keys)
		{
			if (root == null)
				return null;

			int subIndex = root.keys.Count - 1 + 1;
			foreach (var item in root.Map)
			{
				if (item.Key.Equals(keys[subIndex]))
				{
					if (subIndex == keys.Count - 1)
					{
						return item.Value;
					}
					return Find(item.Value, keys);
				}
			}

			return null;
		}

		private MultiTreeNode<T> Find(MultiTreeNode<T> root, T value, Func<MultiTreeNode<T>, T, bool> func)
		{
			if (root == null)
				return null;

			foreach (var item in root.Map)
			{
				if (value.Equals(item.Value.value))
					return item.Value;
				if (func(item.Value, value))
				{
					MultiTreeNode<T> node = Find(item.Value, value, func);
					if (node != null) return node;
				}
			}
			return null;
		}


		private void Delete(MultiTreeNode<T> root, T value)
		{
			if (root == null)
				return;

			bool hasFind = false;
			object key = null;
			foreach (var item in root.Map)
			{
				if (value.Equals(item.Value.value))
				{
					hasFind = true;
					key = item.Key;
					break;
				}
				Delete(item.Value, value);

			}

			if (hasFind)
				root.Map.Remove(key);
		}

		private void Delete(MultiTreeNode<T> root, T value, Func<MultiTreeNode<T>, T, bool> func)
		{
			if (root == null)
				return;

			bool hasFind = false;
			object key = null;
			foreach (var item in root.Map)
			{
				if (value.Equals(item.Value.value))
				{
					hasFind = true;
					key = item.Key;
					break;
				}

				if (func(root, value))
				{
					Delete(item.Value, value, func);
				}

			}

			if (hasFind)
				root.Map.Remove(key);
		}


		private void GetAllNode(MultiTreeNode<T> node, List<MultiTreeNode<T>> values, bool onlyLeaf = true)
		{
			if (AddNode_IfSkip(node, values, onlyLeaf))
				return;

			foreach (var item in node.Map)
			{
				GetAllNode(item.Value, values, onlyLeaf);
			}
		}

		private void GetAllNode(MultiTreeNode<T> node, List<MultiTreeNode<T>> values, Func<MultiTreeNode<T>, bool> func, bool onlyLeaf = true)
		{
			if (AddNode_IfSkip(node, values, onlyLeaf))
				return;

			foreach (var item in node.Map)
			{
				if (func(item.Value))
					GetAllNode(item.Value, values, func, onlyLeaf);
			}
		}

		private void GetAllNodeValue(MultiTreeNode<T> node, List<T> values, bool onlyLeaf = true)
		{
			if (AddNodeValue_IfSkip(node, values, onlyLeaf))
				return;

			foreach (var item in node.Map)
			{
				GetAllNodeValue(item.Value, values, onlyLeaf);
			}
		}

		private bool AddNode_IfSkip(MultiTreeNode<T> node, List<MultiTreeNode<T>> values, bool onlyLeaf = true)
		{
			if (node == null) return true;

			bool isLeaf = node.Map.Count == 0;
			if (isLeaf)
			{
				values.Add(node);
				return true;
			}

			if (!onlyLeaf)
				values.Add(node);
			return false;
		}

		private bool AddNodeValue_IfSkip(MultiTreeNode<T> node, List<T> values, bool onlyLeaf = true)
		{
			bool isLeaf = node.Map.Count == 0;

			if (isLeaf)
			{
				values.Add(node.value);
				return true;
			}


			if (!onlyLeaf && node.value != null)
				values.Add(node.value);

			return false;
		}
	}
}
